// ----------------------------------------------------------------------------
// sort_stack.h
// ----------------------------------------------------------------------------
/*
 Description:
 最小のデータを取り出す際にO(1)でデータを取得できるスタック構造.
 データを積み上げる時よりも、条件に沿ったデータを取り出すことが頻繁にある場合、
 このコンテナが有用かもしれない.
 ※このコンテナはスレッドセーフではない.
 
 ----------------------------------------------------------------
 使い方.
 
 1. データ型と、比較用プレディケートオブジェクトを指定する.
 デフォルトでは、std::lessが利用されている. 
 
    typedef SortStack<int> MinStack_Int;
 
 2. データに任意のエレメントを追加していく. 
    Bestを呼び出すことで比較条件で最も優れたエレメントを取得できる.
 
    MinStack_Int s;
 
    s.Push(1);
    s.Push(6);
    s.Push(3);
 
    int value = s.Best();
    assert(value == 1);
 
 */
#pragma once
#include <deque>
#include <functional>   // std::less, std::greater etc.
#include <utility>      // std::pair

namespace fw
{
    template < typename T, typename Comparator = std::less<T> > class SortStack
    {
    private:
        
        std::deque< std::pair<T, size_t> >  m_stack;
        Comparator                          m_comp;
                
    public:
        explicit        SortStack(Comparator c=Comparator())
        : m_stack()
        , m_comp (c)
        {
        }
        
        void            Push(const T& v)
        {
            if(Empty())
            {
                m_stack.push_back(std::make_pair(v, 0));
            }
            else
            {
                size_t bestIndex = (m_comp(v, Best())) ? m_stack.size() : m_stack.back().second;
                m_stack.push_back(std::make_pair(v, bestIndex));
            }
        }
        
        void            Pop()
        {
            m_stack.pop_back();
        }
        
        const T&        Top() const
        {
            return m_stack.back().first;
        }
        
        const T&        Best() const
        {   // 最も条件に沿ったエレメントのインデックスは常に先頭のエレメントのインデックスで参照できる.
            return m_stack[m_stack.back().second].first;
        }
        
        bool            Empty() const
        {
            return m_stack.empty();
        }
        
        size_t          Size() const
        {
            return m_stack.size();
        }
        
    }; // class SortStack 
    
} // namespace fw 

